SherbyNet - /page/wikibook/entry.mu

Micron Document

<!DOCTYPE html>

<title>Recursive descent parser</title>

</head>

Recursive descent parser

</h1>

</header>

/* start https://en.wikipedia.org/ */

.mw-parser-output .ambox{border:1px solid #a2a9b1;border-left:10px solid #36c;background-color:#fbfbfb;box-sizing:border-box}.mw-parser-output .ambox+link+.ambox,.mw-parser-output .ambox+link+style+.ambox,.mw-parser-output .ambox+link+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+style+.ambox,.mw-parser-output .ambox+.mw-empty-elt+link+link+.ambox{margin-top:-1px}html body.mediawiki .mw-parser-output .ambox.mbox-small-left{margin:4px 1em 4px 0;overflow:hidden;width:238px;border-collapse:collapse;font-size:88%;line-height:1.25em}.mw-parser-output .ambox-speedy{border-left:10px solid #b32424;background-color:#fee7e6}.mw-parser-output .ambox-delete{border-left:10px solid #b32424}.mw-parser-output .ambox-content{border-left:10px solid #f28500}.mw-parser-output .ambox-style{border-left:10px solid #fc3}.mw-parser-output .ambox-move{border-left:10px solid #9932cc}.mw-parser-output .ambox-protection{border-left:10px solid #a2a9b1}.mw-parser-output .ambox .mbox-text{border:none;padding:0.25em 0.5em;width:100%}.mw-parser-output .ambox .mbox-image{border:none;padding:2px 0 2px 0.5em;text-align:center}.mw-parser-output .ambox .mbox-imageright{border:none;padding:2px 0.5em 2px 0;text-align:center}.mw-parser-output .ambox .mbox-empty-cell{border:none;padding:0;width:1px}.mw-parser-output .ambox .mbox-image-div{width:52px}@media(min-width:720px){.mw-parser-output .ambox{margin:0 10%}}@media print{body.ns-0 .mw-parser-output .ambox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style>

In <a href="Computer_science" title="Computer science">computer science</a>, a recursive descent parser is a kind of <a href="Top-down_parsing" title="Top-down parsing">top-down parser</a> built from a set of <a href="Mutual_recursion" title="Mutual recursion">mutually recursive</a> procedures (or a non-recursive equivalent) where each such <a href="Procedure_(computer_science)" class="mw-redirect" title="Procedure (computer science)">procedure</a> implements one of the <a href="Terminal_and_nonterminal_symbols" title="Terminal and nonterminal symbols">nonterminals</a> of the <a href="Formal_grammar" title="Formal grammar">grammar</a>. Thus the structure of the resulting program closely mirrors that of the grammar it recognizes.<a href="#cite_note-1">[1]</a><a href="#cite_note-2">[2]</a>

A predictive parser is a recursive descent parser that does not require <a href="Backtracking" title="Backtracking">backtracking</a>.<a href="#cite_note-Watson2017-3">[3]</a> Predictive parsing is possible only for the class of <a href="LL_parser" title="LL parser">LL(k)</a> grammars, which are the <a href="Context-free_grammar" title="Context-free grammar">context-free grammars</a> for which there exists some positive integer k that allows a recursive descent parser to decide which production to use by examining only the next k tokens of input. The LL(k) grammars therefore exclude all <a href="Ambiguous_grammar" title="Ambiguous grammar">ambiguous grammars</a>, as well as all grammars that contain <a href="Left_recursion" title="Left recursion">left recursion</a>. Any context-free grammar can be transformed into an equivalent grammar that has no left recursion, but removal of left recursion does not always yield an LL(k) grammar. A predictive parser runs in <a href="Linear_time" class="mw-redirect" title="Linear time">linear time</a>.

Recursive descent with backtracking is a technique that determines which <a href="Production_rule_(formal_languages)" class="mw-redirect" title="Production rule (formal languages)">production</a> to use by trying each production in turn. Recursive descent with backtracking is not limited to LL(k) grammars, but is not guaranteed to terminate unless the grammar is LL(k). Even when they terminate, parsers that use recursive descent with backtracking may require <a href="Exponential_time" class="mw-redirect" title="Exponential time">exponential time</a>.

Although predictive parsers are widely used, and are frequently chosen if writing a parser by hand, programmers often prefer to use a table-based parser produced by a <a href="Parser_generator" class="mw-redirect" title="Parser generator">parser generator</a>, either for an LL(k) language or using an alternative parser, such as <a href="LALR_parser" title="LALR parser">LALR</a> or <a href="LR_parser" title="LR parser">LR</a>. This is particularly the case if a grammar is not in <a href="LL_parser" title="LL parser">LL(k)</a> form, as transforming the grammar to LL to make it suitable for predictive parsing is involved. Predictive parsers can also be automatically generated, using tools like <a href="ANTLR" title="ANTLR">ANTLR</a>.

Predictive parsers can be depicted using transition diagrams for each non-terminal symbol where the edges between the initial and the final states are labelled by the symbols (terminals and non-terminals) of the right side of the production rule.<a href="#cite_note-4">[4]</a>

<div class="mw-heading mw-heading2"><h2 id="Example_parser">Example parser</h2></div>

The following <a href="Extended_Backus%E2%80%93Naur_Form" class="mw-redirect" title="Extended Backus–Naur Form">EBNF</a>-like <a href="Formal_grammar" title="Formal grammar">grammar</a> (for <a href="Niklaus_Wirth" title="Niklaus Wirth">Niklaus Wirth</a>'s <a href="PL/0" title="PL/0">PL/0</a> programming language, from <a href="Algorithms_%2B_Data_Structures_%3D_Programs" title="Algorithms + Data Structures = Programs">Algorithms + Data Structures = Programs</a>) is in <a href="LL_parser" title="LL parser">LL(1)</a> form:

<div class="mw-highlight mw-highlight-lang-ebnf mw-content-ltr" dir="ltr"><pre> program = block "." .

block =

["const" ident "=" number {"," ident "=" number} ";"]

["var" ident {"," ident} ";"]

{"procedure" ident ";" block ";"} statement .

statement =

ident ":=" expression

| "call" ident

| "begin" statement {";" statement } "end"

| "if" condition "then" statement

| "while" condition "do" statement .

condition =

"odd" expression

| expression ("="|"#"|"<"|"<="|">"|">=") expression .

expression = ["+"|"-"] term {("+"|"-") term} .

term = factor {("*"|"/") factor} .

factor =

ident

| number

| "(" expression ")" .

</pre></div>

<a href="Terminal_symbol" class="mw-redirect" title="Terminal symbol">Terminals</a> are expressed in quotes. Each <a href="Nonterminal_symbol" class="mw-redirect" title="Nonterminal symbol">nonterminal</a> is defined by a rule in the grammar, except for ident and number, which are assumed to be implicitly defined.

<div class="mw-heading mw-heading3"><h3 id="C_implementation">C implementation</h3></div>

What follows is an implementation of a recursive descent parser for the above language in <a href="C_(programming_language)" title="C (programming language)">C</a>. The parser reads in source code, and exits with an error message if the code fails to parse, exiting silently if the code parses correctly.

Notice how closely the predictive parser below mirrors the grammar above. There is a procedure for each nonterminal in the grammar. Parsing descends in a top-down manner until the final nonterminal has been processed. The program fragment depends on a global variable, sym, which contains the current symbol from the input, and the function nextsym, which updates sym when called.

The implementations of the functions nextsym and error are omitted for simplicity.

<div class="mw-highlight mw-highlight-lang-c mw-content-ltr" dir="ltr"><pre>typedef enum {ident, number, lparen, rparen, times, slash, plus,

minus, eql, neq, lss, leq, gtr, geq, callsym, beginsym, semicolon,

endsym, ifsym, whilesym, becomes, thensym, dosym, constsym, comma,

varsym, procsym, period, oddsym} Symbol;

Symbol sym;

void nextsym(void);

void error(const char msg[]);

int accept(Symbol s) {

nextsym();

return 1;

}

return 0;

}

int expect(Symbol s) {

if (accept(s))

return 1;

error("expect: unexpected symbol");

return 0;

}

void factor(void) {

if (accept(ident)) {

;

} else if (accept(number)) {

;

} else if (accept(lparen)) {

expression();

expect(rparen);

} else {

error("factor: syntax error");

nextsym();

}

}

void term(void) {

factor();

while (sym == times || sym == slash) {

nextsym();

factor();

}

}

void expression(void) {

nextsym();

term();

while (sym == plus || sym == minus) {

nextsym();

term();

}

}

void condition(void) {

if (accept(oddsym)) {

expression();

} else {

expression();

if (sym == eql || sym == neq || sym == lss || sym == leq || sym == gtr || sym == geq) {

nextsym();

expression();

} else {

error("condition: invalid operator");

nextsym();

}

}

void statement(void) {

expect(becomes);

expression();

} else if (accept(callsym)) {

expect(ident);

} else if (accept(beginsym)) {

do {

statement();

} while (accept(semicolon));

expect(endsym);

} else if (accept(ifsym)) {

condition();

expect(thensym);

statement();

} else if (accept(whilesym)) {

condition();

expect(dosym);

statement();

} else {

error("statement: syntax error");

nextsym();

}

}

void block(void) {

if (accept(constsym)) {

do {

expect(ident);

expect(eql);

expect(number);

expect(semicolon);

}

if (accept(varsym)) {

do {

expect(ident);

expect(semicolon);

}

while (accept(procsym)) {

expect(ident);

expect(semicolon);

block();

expect(semicolon);

}

statement();

}

void program(void) {

nextsym();

block();

expect(period);

}

</pre></div>

<div class="mw-heading mw-heading2"><h2 id="Examples">Examples</h2></div>

Some recursive descent parser generators:

<ul><li><a href="TMG_(language)" title="TMG (language)">TMG</a> – an early compiler-compiler used in the 1960s and early 1970s</li>

<li><a href="JavaCC" title="JavaCC">JavaCC</a></li>

<li><a href="ANTLR" title="ANTLR">ANTLR</a></li>

<li><a href="Spirit_Parser_Framework" title="Spirit Parser Framework">Spirit Parser Framework</a> – a C++ recursive descent parser generator framework requiring no pre-compile step</li>

<li><a href="Parboiled_(Java)" title="Parboiled (Java)">parboiled (Java)</a> – a recursive descent <a href="Parsing_expression_grammar" title="Parsing expression grammar">PEG</a> parsing library for <a href="Java_(programming_language)" title="Java (programming language)">Java</a></li></ul>

The c++ front-end of the <a href="Clang" title="Clang">Clang</a> compiler contains a hand-written parser based on the recursive-descent parsing algorithm. <a href="#cite_note-5">[5]</a>

<ul><li><a href="Parser_combinator" title="Parser combinator">Parser combinator</a> – a higher-order function used in combinatory parsing, a method of factoring recursive descent parser designs</li>

<li><a href="Parsing_expression_grammar" title="Parsing expression grammar">Parsing expression grammar</a> – another form representing recursive descent grammar</li>

<li><a href="Recursive_ascent_parser" title="Recursive ascent parser">Recursive ascent parser</a></li>

<li><a href="Tail_recursive_parser" title="Tail recursive parser">Tail recursive parser</a> – a variant of the recursive descent parser</li></ul>

<div class="mw-heading mw-heading2"><h2 id="References">References</h2></div>

/* start https://en.wikipedia.org/ */

.mw-parser-output .reflist{margin-bottom:0.5em;list-style-type:decimal}@media screen{.mw-parser-output .reflist{font-size:90%}}.mw-parser-output .reflist .references{font-size:100%;margin-bottom:0;list-style-type:inherit}.mw-parser-output .reflist-columns-2{column-width:30em}.mw-parser-output .reflist-columns-3{column-width:25em}.mw-parser-output .reflist-columns{margin-top:0.3em}.mw-parser-output .reflist-columns ol{margin-top:0}.mw-parser-output .reflist-columns li{page-break-inside:avoid;break-inside:avoid-column}.mw-parser-output .reflist-upper-alpha{list-style-type:upper-alpha}.mw-parser-output .reflist-upper-roman{list-style-type:upper-roman}.mw-parser-output .reflist-lower-alpha{list-style-type:lower-alpha}.mw-parser-output .reflist-lower-greek{list-style-type:lower-greek}.mw-parser-output .reflist-lower-roman{list-style-type:lower-roman}

/* end https://en.wikipedia.org/ */

</style><div class="reflist">

/* start https://en.wikipedia.org/ */

.mw-parser-output .citation{word-wrap:break-word}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}

/* end https://en.wikipedia.org/ */

</style>This article is based on material taken from <a rel="nofollow" class="external text" href="https://foldoc.org/Recursive+descent+parser">Recursive+descent+parser</a> at the <a href="Free_On-line_Dictionary_of_Computing" title="Free On-line Dictionary of Computing">Free On-line Dictionary of Computing</a> prior to 1 November 2008 and incorporated under the "relicensing" terms of the <a href="GNU_Free_Documentation_License" title="GNU Free Documentation License">GFDL</a>, version 1.3 or later.

</li>

/* start https://en.wikipedia.org/ */

.mw-parser-output cite.citation{font-style:inherit;word-wrap:break-word}.mw-parser-output .citation q{quotes:"\"""\"""'""'"}.mw-parser-output .citation:target{background-color:rgba(0,127,255,0.133)}.mw-parser-output .id-lock-free.id-lock-free a{background:url("./mw/Lock-green.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-limited.id-lock-limited a,.mw-parser-output .id-lock-registration.id-lock-registration a{background:url("./mw/Lock-gray-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .id-lock-subscription.id-lock-subscription a{background:url("./mw/Lock-red-alt-2.svg")right 0.1em center/9px no-repeat}.mw-parser-output .cs1-ws-icon a{background:url("./mw/Wikisource-logo.svg")right 0.1em center/12px no-repeat}body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-free a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-limited a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-registration a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .id-lock-subscription a,body:not(.skin-timeless):not(.skin-minerva) .mw-parser-output .cs1-ws-icon a{background-size:contain;padding:0 1em 0 0}.mw-parser-output .cs1-code{color:inherit;background:inherit;border:none;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;color:var(--color-error,#d33)}.mw-parser-output .cs1-visible-error{color:var(--color-error,#d33)}.mw-parser-output .cs1-maint{display:none;color:#085;margin-left:0.3em}.mw-parser-output .cs1-kern-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right{padding-right:0.2em}.mw-parser-output .citation .mw-selflink{font-weight:inherit}@media screen{.mw-parser-output .cs1-format{font-size:95%}html.skin-theme-clientpref-night .mw-parser-output .cs1-maint{color:#18911f}}@media screen and (prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .cs1-maint{color:#18911f}}

/* end https://en.wikipedia.org/ */

</style><cite id="CITEREFBurge,_W.H.1975" class="citation book cs1">Burge, W.H. (1975). <a rel="nofollow" class="external text" href="https://archive.org/details/recursiveprogram0000burg">Recursive Programming Techniques</a>. Addison-Wesley Publishing Company. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-201-14450-6</bdi>.</cite>

</li>

<li id="cite_note-Watson2017-3"><a href="#cite_ref-Watson2017_3-0">^</a> <cite id="CITEREFWatson2017" class="citation book cs1">Watson, Des (22 March 2017). <a rel="nofollow" class="external text" href="https://books.google.com/books?id=05B0DgAAQBAJ&q=%22predictive+parser%22">A Practical Approach to Compiler Construction</a>. Springer. <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>978-3-319-52789-5</bdi>.</cite>

</li>

<li id="cite_note-4"><a href="#cite_ref-4">^</a> <cite id="CITEREFAhoSethiUllman1986" class="citation book cs1"><a href="Alfred_V._Aho" class="mw-redirect" title="Alfred V. Aho">Aho, Alfred V.</a>; Sethi, Ravi; <a href="Jeffrey_Ullman" title="Jeffrey Ullman">Ullman, Jeffrey</a> (1986). <a rel="nofollow" class="external text" href="https://archive.org/details/compilers00ahoa">Compilers: Principles, Techniques and Tools</a> (first ed.). Addison Wesley. p. <a rel="nofollow" class="external text" href="https://archive.org/details/compilers00ahoa/page/n193">183</a>.</cite>

</li>

<li id="cite_note-5"><a href="#cite_ref-5">^</a> How Clang handles the type / variable name ambiguity of C/C++

<a rel="nofollow" class="external free" href="https://eli.thegreenplace.net/2012/07/05/how-clang-handles-the-type-variable-name-ambiguity-of-cc/">https://eli.thegreenplace.net/2012/07/05/how-clang-handles-the-type-variable-name-ambiguity-of-cc/</a>

</li>

</ol></div></div>

<div class="mw-heading mw-heading3"><h3 id="General_references">General references</h3></div>

<ul><li><a href="Compilers%3A_Principles%2C_Techniques%2C_and_Tools" title="Compilers: Principles, Techniques, and Tools">Compilers: Principles, Techniques, and Tools</a>, first edition, Alfred V Aho, Ravi Sethi, and Jeffrey D Ullman, in particular Section 4.4.</li>

<li>Modern Compiler Implementation in Java, Second Edition, Andrew Appel, 2002, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-521-82060-X</bdi>.</li>

<li>Recursive Programming Techniques, W.H. Burge, 1975, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-201-14450-6</bdi></li>

<li>Crafting a Compiler with C, Charles N Fischer and Richard J LeBlanc, Jr, 1991, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-8053-2166-7</bdi>.</li>

<li>Compiling with C# and Java, Pat Terry, 2005, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-321-26360-X</bdi>, 624</li>

<li>Algorithms + Data Structures = Programs, Niklaus Wirth, 1975, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-13-022418-9</bdi></li>

<li>Compiler Construction, Niklaus Wirth, 1996, <a href="ISBN_(identifier)" class="mw-redirect" title="ISBN (identifier)">ISBN</a> <bdi>0-201-40353-6</bdi></li></ul>

<div class="mw-heading mw-heading2"><h2 id="External_links">External links</h2></div>

<ul><li><a rel="nofollow" class="external text" href="https://compilers.iecc.com/crenshaw/">Jack W. Crenshaw: Let's Build A Compiler (1988-1995)</a>, in <a href="Pascal_(programming_language)" title="Pascal (programming language)">Pascal</a>, with <a href="Assembly_language" title="Assembly language">assembly language</a> output, using a "keep it simple" approach</li></ul>

/* start https://en.wikipedia.org/ */

.mw-parser-output .hlist dl,.mw-parser-output .hlist ol,.mw-parser-output .hlist ul{margin:0;padding:0}.mw-parser-output .hlist dd,.mw-parser-output .hlist dt,.mw-parser-output .hlist li{margin:0;display:inline}.mw-parser-output .hlist.inline,.mw-parser-output .hlist.inline dl,.mw-parser-output .hlist.inline ol,.mw-parser-output .hlist.inline ul,.mw-parser-output .hlist dl dl,.mw-parser-output .hlist dl ol,.mw-parser-output .hlist dl ul,.mw-parser-output .hlist ol dl,.mw-parser-output .hlist ol ol,.mw-parser-output .hlist ol ul,.mw-parser-output .hlist ul dl,.mw-parser-output .hlist ul ol,.mw-parser-output .hlist ul ul{display:inline}.mw-parser-output .hlist .mw-empty-li{display:none}.mw-parser-output .hlist dt::after{content:": "}.mw-parser-output .hlist dd::after,.mw-parser-output .hlist li::after{content:" · ";font-weight:bold}.mw-parser-output .hlist dd:last-child::after,.mw-parser-output .hlist dt:last-child::after,.mw-parser-output .hlist li:last-child::after{content:none}.mw-parser-output .hlist dd dd:first-child::before,.mw-parser-output .hlist dd dt:first-child::before,.mw-parser-output .hlist dd li:first-child::before,.mw-parser-output .hlist dt dd:first-child::before,.mw-parser-output .hlist dt dt:first-child::before,.mw-parser-output .hlist dt li:first-child::before,.mw-parser-output .hlist li dd:first-child::before,.mw-parser-output .hlist li dt:first-child::before,.mw-parser-output .hlist li li:first-child::before{content:" (";font-weight:normal}.mw-parser-output .hlist dd dd:last-child::after,.mw-parser-output .hlist dd dt:last-child::after,.mw-parser-output .hlist dd li:last-child::after,.mw-parser-output .hlist dt dd:last-child::after,.mw-parser-output .hlist dt dt:last-child::after,.mw-parser-output .hlist dt li:last-child::after,.mw-parser-output .hlist li dd:last-child::after,.mw-parser-output .hlist li dt:last-child::after,.mw-parser-output .hlist li li:last-child::after{content:")";font-weight:normal}.mw-parser-output .hlist ol{counter-reset:listitem}.mw-parser-output .hlist ol>li{counter-increment:listitem}.mw-parser-output .hlist ol>li::before{content:" "counter(listitem)"\a0 "}.mw-parser-output .hlist dd ol>li:first-child::before,.mw-parser-output .hlist dt ol>li:first-child::before,.mw-parser-output .hlist li ol>li:first-child::before{content:" ("counter(listitem)"\a0 "}

/* end https://en.wikipedia.org/ */

</style><style data-mw-deduplicate="TemplateStyles:r1236075235">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbox{box-sizing:border-box;border:1px solid #a2a9b1;width:100%;clear:both;font-size:88%;text-align:center;padding:1px;margin:1em auto 0}.mw-parser-output .navbox .navbox{margin-top:0}.mw-parser-output .navbox+.navbox,.mw-parser-output .navbox+.navbox-styles+.navbox{margin-top:-1px}.mw-parser-output .navbox-inner,.mw-parser-output .navbox-subgroup{width:100%}.mw-parser-output .navbox-group,.mw-parser-output .navbox-title,.mw-parser-output .navbox-abovebelow{padding:0.25em 1em;line-height:1.5em;text-align:center}.mw-parser-output .navbox-group{white-space:nowrap;text-align:right}.mw-parser-output .navbox,.mw-parser-output .navbox-subgroup{background-color:#fdfdfd}.mw-parser-output .navbox-list{line-height:1.5em;border-color:#fdfdfd}.mw-parser-output .navbox-list-with-group{text-align:left;border-left-width:2px;border-left-style:solid}.mw-parser-output tr+tr>.navbox-abovebelow,.mw-parser-output tr+tr>.navbox-group,.mw-parser-output tr+tr>.navbox-image,.mw-parser-output tr+tr>.navbox-list{border-top:2px solid #fdfdfd}.mw-parser-output .navbox-title{background-color:#ccf}.mw-parser-output .navbox-abovebelow,.mw-parser-output .navbox-group,.mw-parser-output .navbox-subgroup .navbox-title{background-color:#ddf}.mw-parser-output .navbox-subgroup .navbox-group,.mw-parser-output .navbox-subgroup .navbox-abovebelow{background-color:#e6e6ff}.mw-parser-output .navbox-even{background-color:#f7f7f7}.mw-parser-output .navbox-odd{background-color:transparent}.mw-parser-output .navbox .hlist td dl,.mw-parser-output .navbox .hlist td ol,.mw-parser-output .navbox .hlist td ul,.mw-parser-output .navbox td.hlist dl,.mw-parser-output .navbox td.hlist ol,.mw-parser-output .navbox td.hlist ul{padding:0.125em 0}.mw-parser-output .navbox .navbar{display:block;font-size:100%}.mw-parser-output .navbox-title .navbar{float:left;text-align:left;margin-right:0.5em}body.skin--responsive .mw-parser-output .navbox-image img{max-width:none!important}@media print{body.ns-0 .mw-parser-output .navbox{display:none!important}}

/* end https://en.wikipedia.org/ */

</style></div><div role="navigation" class="navbox" aria-labelledby="Parsing_algorithms116" style="padding:3px"><table class="nowraplinks mw-collapsible autocollapse navbox-inner" style="border-spacing:0;background:transparent;color:inherit"><tbody><tr><th scope="col" class="navbox-title" colspan="2"><style data-mw-deduplicate="TemplateStyles:r1239400231">

/* start https://en.wikipedia.org/ */

.mw-parser-output .navbar{display:inline;font-size:88%;font-weight:normal}.mw-parser-output .navbar-collapse{float:left;text-align:left}.mw-parser-output .navbar-boxtext{word-spacing:0}.mw-parser-output .navbar ul{display:inline-block;white-space:nowrap;line-height:inherit}.mw-parser-output .navbar-brackets::before{margin-right:-0.125em;content:"[ "}.mw-parser-output .navbar-brackets::after{margin-left:-0.125em;content:" ]"}.mw-parser-output .navbar li{word-spacing:-0.125em}.mw-parser-output .navbar a>span,.mw-parser-output .navbar a>abbr{text-decoration:inherit}.mw-parser-output .navbar-mini abbr{font-variant:small-caps;border-bottom:none;text-decoration:none;cursor:inherit}.mw-parser-output .navbar-ct-full{font-size:114%;margin:0 7em}.mw-parser-output .navbar-ct-mini{font-size:114%;margin:0 4em}html.skin-theme-clientpref-night .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}@media(prefers-color-scheme:dark){html.skin-theme-clientpref-os .mw-parser-output .navbar li a abbr{color:var(--color-base)!important}}@media print{.mw-parser-output .navbar{display:none!important}}

/* end https://en.wikipedia.org/ */

</style><div id="Parsing_algorithms116" style="font-size:114%;margin:0 4em"><a href="Parsing" title="Parsing">Parsing algorithms</a></div></th></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Top-down_parsing" title="Top-down parsing">Top-down</a></th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Earley_parser" title="Earley parser">Earley</a></li>

<li>

<ul><li><a href="Tail_recursive_parser" title="Tail recursive parser">Tail recursive</a></li></ul></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%"><a href="Bottom-up_parsing" title="Bottom-up parsing">Bottom-up</a></th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li>Precedence

<ul><li><a href="Simple_precedence_parser" class="mw-redirect" title="Simple precedence parser">Simple</a></li>

<li><a href="Operator-precedence_parser" title="Operator-precedence parser">Operator</a>

<ul><li><a href="Shunting_yard_algorithm" title="Shunting yard algorithm">Shunting-yard</a></li></ul></li></ul></li>

<ul><li><a href="Simple_LR_parser" title="Simple LR parser">Simple</a></li>

<li><a href="LALR_parser" title="LALR parser">Look-ahead</a></li>

<li><a href="Canonical_LR_parser" title="Canonical LR parser">Canonical</a></li>

<li><a href="GLR_parser" title="GLR parser">Generalized</a></li></ul></li>

<li><a href="Recursive_ascent_parser" title="Recursive ascent parser">Recursive ascent</a></li>

<li><a href="Shift-reduce_parser" title="Shift-reduce parser">Shift-reduce</a></li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Mixed, other</th><td class="navbox-list-with-group navbox-list navbox-odd hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<ul><li><a href="Parser_combinator" title="Parser combinator">Combinator</a></li>

<li><a href="Chart_parser" title="Chart parser">Chart</a>

<ul><li><a href="Left_corner_parser" title="Left corner parser">Left corner</a></li></ul></li>

<li>Statistical</li></ul>

</div></td></tr><tr><th scope="row" class="navbox-group" style="width:1%">Related topics</th><td class="navbox-list-with-group navbox-list navbox-even hlist" style="width:100%;padding:0"><div style="padding:0 0.25em">

<li><a href="Definite_clause_grammar" title="Definite clause grammar">Definite clause grammar</a></li>

<li><a href="Deterministic_parsing" title="Deterministic parsing">Deterministic parsing</a></li>

<li><a href="Dynamic_programming" title="Dynamic programming">Dynamic programming</a></li>

<li><a href="Memoization" title="Memoization">Memoization</a></li>

<li><a href="Compiler-compiler" title="Compiler-compiler">Parser generator</a>

<li><a href="Parse_tree" title="Parse tree">Parse tree</a></li>

<li><a href="Scannerless_parsing" title="Scannerless parsing">Scannerless parsing</a></li>

<li><a href="History_of_compiler_construction" title="History of compiler construction">History of compiler construction</a></li>

<li><a href="Comparison_of_parser_generators" title="Comparison of parser generators">Comparison of parser generators</a></li>

<li><a href="Operator-precedence_grammar" title="Operator-precedence grammar">Operator-precedence grammar</a></li></ul>

</div></td></tr></tbody></table></div></div><div><div class="zim-footer">

This article is issued from <a class="external text" title="Last edited on 2025-07-16" href="https://en.wikipedia.org/wiki/?title=Recursive_descent_parser&oldid=1300802119">Wikipedia</a>. The text is available under <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.en">Creative Commons Attribution-Share Alike 4.0</a> unless otherwise noted. Additional terms may apply for the media files.

</div>

</div></div>

</div>

</main>

</div>

</body></html>